Binary Search Trees

What is a binary search tree?

• We can represent such a tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right, and p.
• The root node is the only node in the tree whose parent is NIL.
• The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:
  • Let be a node in a binary search tree. If is a node in the left subtree of , then . If is a node in the right subtree of , then .
• The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk.Similarly, a preorder tree walk and postorder tree walk

INORDER-TREE-WALK（x） 
1 if x ≠ NIL 
2    INORDER-TREE-WALK （x.left） 
3    print x.key 
4    INORDER-TREE-WALK （x.right）

• Theorem 12.1:If is the root of an n-node subtree, then the call INORDER-TREE-WALK(x) takes time.

Querying a binary search tree

Searching

TREE-SEARCH（x,k） 
1 if x == NIL or k == x.key 
2     return x 
3 if k <x.key 
4     return TREE-SEARCH（x.left, k） 
5 else return TREE-SEARCH（x.right, k）

ITERATIVE-TREE-SEARCH（x,k） 
1 while x ≠ NIL and k ≠x.key 
2     if k < x.key 
3        x = x.left 
4     else x = x.right 
5 return x

Minimum and maximum

TREE-MINIMUM （x） 
1 while x.left ≠ NIL 
2       x = x.left 
3 return x

TREE-MAXIMUM（x） 
1 while x.right ≠ NIL 
2       x = x.right 
3 return x

Successor and predecessor

• the successor of a node x is the node with the smallest key greater than x.key

  TREE-SUCCESSOR（x） 
  1 if x.right ≠ NIL 
  2    return TREE-MINIMUM （x.right） 
  3 y=x.p
  4 while y ≠ NIL and x== y.right
  5    x=y
  6    y=y.p
  7 return y

• Theorem 12.2:We can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR so that each one runs in time on a binary search tree of height .

Insertion and deletion

Insertion

TREE-INSERT（T，z ） 
1 y = NIL 
2 x= T.root 
3 while x ≠ NIL 
4     y=x 
5     if z.key < x.key 
6        x= x.left 
7     else x= x.right 
8 z.p=y
9 if y== NIL 
10    T.root = z // tree T was empty
11 elseif z.key < y.key 
12    y.left =z 
13 else y.right=z

Deletion

The overall strategy for deleting a node from a binary search tree has three basic cases but, as we shall see, one of the cases is a bit tricky. - If has no children, then we simply remove it by modifying its parent to replace with NIL as its child. - If has just one child, then we elevate that child to take position in the tree by modifying parent to replace by child. - If has two children, then we find successor —which must be in right subtree-and have take position in the tree. The rest of original right subtree becomes new right subtree, and left subtree becomes new left subtree. This case is the tricky one because, as we shall see, it matters whether is right child.

When TRANSPLANT replaces the subtree rooted at node with the subtree rooted at node , node parent becomes node parent, and parent ends up having as its appropriate child

TRANSPLANT（T,u,v） 
1 if u.p == NIL 
2    T.root = v 
3 elseif u == u.p.left 
4    u.p.left =v 
5 else u.p.right=v 
6 if v ≠ NIL 
7    v.p = u.p

TREE-DELETE（T,z） 
1 if z.left==NIL
2    TRANSPLANT(T,z,z.right)
3 elseif z.right==NIL
4    TRANSPLANT(T,z,z.left)
5 else y=TREE-MINIMUM(z.right)
6    if y.p≠z
7       TRANSPLANT(T,y,y.right)
8       y.right = z.right
9.      y.right.p=y
10   TRANSPLANT(T,z,y)
11   y.left =z.left
12   y.left.p=y

Randomly built binary search trees